The present invention relates generally to the field of data communications networks and more particularly, to a method and apparatus for source to destination flow control by means of accelerated feedback of network congestion information.
The emergence of the Asynchronous Transfer Mode (ATM) networking protocol is intended as a response to the demand for faster data communications and more sophisticated processing. The ATM protocol relates to a cell based switching and multiplexing technology that is designed to be a general purpose transfer mode for a wide range of traffic services. Communications networks now serve a range of new applications involving mixed media traffic comprising data, voice, still and moving images and video. The aim of the ATM networking protocol is to provide a more flexible facility for the transmission of such traffic and for the allocation of transmission bandwidth in order to efficiently utilize network resources.
The ATM networking protocol is advantageous in that it provides network administrators and end users with multiple classes of communications service. The ATM Forum Traffic Management Working Group has defined five service categories for cell transmission which are distinguished by parameter sets used to describe source behaviour and quality of service (QoS) guarantees. These service categories are identified as constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR), all of which are set out in the Traffic Management Specification, Version 4.0, which was published by the ATM Forum Technical Committee under document no. af-tm-0056.000 in April 1996. An addendum to this specification entitled xe2x80x9cAddendum to Traffic Management V4.0 for ABR parameter negotiationxe2x80x9d was published under document no. af-tm-077.000 in January 1997.
The ABR and UBR service categories are intended to carry data traffic which has no specific cell loss or delay guarantees. The UBR service category is the simplest of the two, as it optionally provides only a guaranteed minimum cell rate. The ABR service category provides source to destination flow control that attempts, but is not guaranteed, to achieve zero cell loss. Thus, the ABR service category offers users a relatively high quality of service in terms of cell loss probability and yet seeks to maintain high network resource utilization. Traffic management techniques such as those adopting flow control are used to protect a network and its various end-systems from congestion in order to achieve network performance and utilization objectives.
Flow control in the ABR service category is achieved by arranging for each source node of a network to send special resource management (RM) cells through the network. The RM cells are typically interleaved with data cells in the network. Each network entity or element, for instance a switch or node in the network, may indicate its congestion status by writing into the RM cell. The RM cell is then forwarded on to the next network element in the data path. At the destination network element, the RM cell is turned back towards the source. The network entities in the backward data path may mark congestion information into the RM cell, which is ultimately received by the source may then adjust its sending rate in response to the information contained in the received RM cell.
The RM cell typically contains three fields which may be written to in order to describe the congestion status of a network entity. First, the cell provides a xe2x80x9cno increasexe2x80x9d (NI) it which indicates that the source must not increase its sending rate. Second, there is provided a congestion indication (CI) bit which indicates that the source must decrease its sending rate. Third, the RM cell contains an explicit rate (ER) field which contains the minimum explicit rate of transmission as may be calculated by any network element in the data path. The concepts of an explicit rate and of algorithms for calculating explicit rates are described in greater detail below. The behaviour of a network source in response to the information contained in these three RM fields is well-known to those skilled in this art.
Various mechanisms can be used in order to achieve flow control in a network. These mechanisms can be classified broadly depending on the congestion monitoring criteria used and the feedback mechanism employed. The feedback mechanisms are either binary in nature or calculate an explicit rate of transmission. In each case flow control information is provided to the source through the RM cell, as explained in greater detail herebelow.
In one method of binary flow control, known to those skilled in this art as Binary ABR, a particular bit in each data cell is set during network congestion. The bit in question is an indicator of forward congestion and is hence known as an Explicit Forward Congestion Indicator bit, or EFCI bit. If a data cell arrives at the network destination node with its EFCI bit set, the node will set an internal variable, known as the CI_State, to a value of 1. Otherwise, the CI_State variable within the node is set to a value of 0. When a resource management cell arrives at the same destination node, and this particular node has its CI_State variable set to a value of 1, the node will set the previously mentioned CI bit in the RM cell also to a value of 1. The RM cell will make its way along the data path to the network source node and this source node will increase its rate of transmission if the CI bit of the arriving RM cell is set to 0, but will decrease its transmission rate if the CI bit of the RM cell is set to 1.
Those skilled in this art will readily appreciate that Binary ABR is a random method of exerting flow control, in that the mechanism cannot control which particular ABR connection will receive restrictive flow control information at any particular point in time. Flow control will therefore vary depending on the instantaneous traffic flow at each contention point in the network. Generally, it is thought that the Binary ABR mechanism is more susceptible to instability in larger networks. Binary feedback schemes where all the connections may share a common FIFO queue may sometimes suffer from unfairness problems depending on the network topology and the source and destination behaviour employed. Given the same level of congestion at all of the switches along a data path, connections travelling more hops have a higher probability of having their EFCI bits set than those travelling a smaller number of hops. Depending on the source and destination behaviour employed, these long hop connections get very few opportunities to increase their rates of transmission and consequently their throughputs are starved. This gives rise to what those in this art have called a xe2x80x9cbeat downxe2x80x9d problem. Potential unfairness problems in binary feedback schemes where all of the virtual connections share a common queue can be alleviated in some cases. For instance, one known enhancement in this regard is to provide separate queues for each virtual connection or for groups of virtual connections.
In explicit rate feedback schemes, a network node such as a switch will perform three important functions. First, the switch will compute the fair share of the network bandwidth that can be supported for a virtual connection. Second, the switch will determine its load. By way of example, this can be done either by monitoring queue lengths or queue growth rates associated with buffering incoming cells. Third, an actual explicit rate of transmission for the connection will be determined by the switch and this information will be sent to the source. Examples of explicit rate switch mechanisms known to those skilled in this art are the Enhanced Proportional Rate Control Algorithm (EPRCA) and two congestion avoidance schemes, namely Explicit Rate Indication for Congestion Avoidance (ERICA) and Congestion Avoidance using Proportional Control (CAPC).
Various explicit rate algorithms have been developed in order to fairly distribute bandwidth between ABR connections. Typically, an explicit rate algorithm may be deployed at every contention point in the data path, namely at every queuing point in the network where the aggregate arrival rate of cells is greater than the aggregate service rate. In the context of an ABR controlled connection, the service rate pertains to the capacity available for the ABR connection, and this capacity is generally time dependent. The ER algorithm attempts to fairly distribute bandwidth between ABR connections at each contention point. For instance, in a Max-Min fairness class of ER algorithms, the goal is to allocate bandwidth at each link in the network so that the link is fully utilized while simultaneously achieving a fair distribution of bandwidth between connections. Each connection will therefore receive an end-to-end bandwidth allocation which is equal to its fair share at the contention point in its connection path through the network where resources are most scarce. A network entity such as a switch may have one or more contention points.
On the establishment of an ABR connection, the end system will specify to the network both a maximum useable bandwidth and a minimum required bandwidth. These are designated typically as the peak cell rate (PCR) and the minimum cell rate (MCR), respectively. ABR flow control occurs between a sending end system and a receiving end system. The sending end system and the receiving end system are connected via bidirectional connections. For each such bidirectional ABR connection, every connection termination point is both a source and a destination. For the forward flow of information from source to destination there exists a control loop consisting of two RM cell flows, one in the forward direction and one in the backward direction. The same holds true for the backward information flow from destination to source.
A network source will generate forward RM cells which are turned around by the destination and sent back to the source as backward RM cells. It is these backward RM cells which carry the feedback information provided by the network elements and/or the destination back to the source. Each network element may directly insert feedback control information into the RM cells when they pass in the forward or backward direction. As well, each network element may indirectly inform the source about congestion by setting the EFCI bit in the data cell header of the cells of the forward information flow. A network element in an impending congested state or in a currently congested state may set an EFCI bit in the cell header so that this indication may be examined by the destination end system. For example, the end system may use this indication to implement a protocol that adaptively lowers the cell rate of the connection during congestion or impending congestion. A network element that is not in a congested state or an impending congested state will not modify the value of this indication. An impending congested state is a state when a network element is operating around its engineered capacity level. Where a cell header contains a set EFCI it, the destination will update the backward RM cells based on this congestion information. As alternatives to inserting feedback control information into RM cells or to the setting of EFCI bits in data cells, each network element may itself generate backward RM cells for flow control.
Like any typical negative feedback control system, the delay in the feedback loop is very important in determining the performance of the controlled system. In the case of the ABR service category which uses explicit rate marking as discussed above, nodal congestion information is marked into the in-band backward RM cell if its value is less than what is being already carried inside cell. As such, the source will always receive the lowest explicit rate values as offered by the nodes that the connection traverses. Thus, the faster the backward RM cells travel back to the source, the quicker the source can respond and hence the better the performance of the feedback mechanism.
Various techniques have been used in the prior art in order to minimize the ER information feedback delay as a backward RM cell travels through a node. One technique involves segmenting an ABR loop by the creation of virtual sources and virtual destinations. This creates a concatenation of sequential virtual ABR control loops, wherein the feedback delay is reduced in each virtual loop. Another known method of reducing ER information feedback delay involves the provision of a dedicated queue for the backward RM cells.
Other techniques for improving ER information feedback involve addressing delays experienced by backward RM cells when such cells experience queuing at various nodes along a connection path. For instance, a network switch which deploys ER based flow control will usually have cell input and output buffers for incoming and outgoing data and RM cells. The backward RM cells in such a configuration may experience unacceptable delays as they are placed in the output queue of the switch, which will normally operate according to a first-in first-out (FIFO) retrieval. These delays are especially prevalent when many virtual connections may be multiplexed into the output queue. Since the ABR service category is often used for bandwidth-on-demand data traffic which seeks to use up all available bandwidth and buffers its network resources as much as possible, congestion of output queues is much more likely with such traffic. It has therefore been proposed in the prior art that backward RM cells be permitted to advance or skip ahead of data cells in the output queues of ATM switches as a means of reducing flow control feedback delay.
Typically, known mechanisms for backward RM cell acceleration have employed a separate queue for such cells, which may be complex or costly to implement, especially where a per-VC queuing structure is to be adopted. As backward RM cells skip ahead of data cells, the intercell spacing of the backward RM cells is no longer observed. This introduces the problem of cell clumping. Thus, one can experience a burst of backward RM cells at one time interval and yet for another interval there is no backward RM cell for carrying congestion information.
There is therefore a need to provide a method and apparatus for ER information acceleration that seeks to alleviate or overcome certain of the problems associated with prior art solutions.
According to a first broad aspect of the present invention, a method of feedback control for adjusting a rate of message transmission over a connection in a communications network is provided. The connection comprises a source and a destination of message transmission. A forward message path begins with the course and ends with the destination, and a backward message path begins with the destination and ends with the source to thereby form a closed loop for the feedback control. The communications network has network elements through which the forward and the backward message paths each traverse. The source is provided with instructions for setting a rate at which the source will transmit messages over the connection, the instructions being transported over the connection by feedback messages received by the source, each of the feedback messages so received containing an explicit rate of transmission each constituting a lowest of a plurality of explicit rates of transmission which correspond to those determined respectively from states of congestion associated with each of the network elements. The method of feedback control comprises the steps of: (a) receiving feedback messages from the backward message path at a network element traversed by the backward message path; (b) extracting an explicit rate of transmission being carried by each of the feedback messages received; (c) storing each of the feedback messages received in a first-in first-out order in a queue; (d) retrieving a feedback message from the head of the queue for transmission from the network element and, substantially at a time when the feedback message retrieved from the head of the queue is to be transmitted externally from the network element, marking the feedback message retrieved from the head of the queue with an explicit rate of transmission determined as a function of an extracted explicit rate pertaining to another feedback message of the feedback messages received more recently received than the feedback message retrieved from the head of the queue and a rate determined from a state of congestion associated with a contention point of the network element; and (e) externally transmitting the feedback message retrieved from the head of the queue from the network element over the backward message path once the feedback message retrieved from the head of the queue has been so marked.
According to a second broad aspect of the present invention, a network element for providing feedback control for adjusting a rate of message transmission over a connection in a communications network is provided. The connection comprises a source and a destination of message transmission. A forward message path of the connection begins with the source and ends with the destination and a backward message path of the connection begins with the destination and ends with the source to thereby form a closed loop for the feedback control. The communications network provides network elements through which the forward and the backward message paths each traverse. The source is provided with instructions for setting a rate at which the source will transmit messages over the connection, the instructions being transported over the connection by feedback messages received by the source, the feedback messages so received containing an explicit rate of transmission constituting a lowest of a plurality of explicit rates of transmission which correspond to those determined respectively from states of congestion associated with each of the network elements. The network element comprises: (a) an input pertaining to the backward message path, wherein the input receives feedback messages from the backward message path; (b) a first memory associated with the input of the backward message path storing the explicit rate of transmission extracted from each of the feedback messages received from the backward message path; (c) a second memory, wherein each of the feedback messages received from the backward message path is stored in said second memory in a first-in first-out order after the explicit rate of transmission is extracted therefrom; (d) an output module pertaining to the backward message path transmitting feedback messages retrieved from said second memory; and wherein a feedback message received is retrieved from the second memory in a first-in first-out order and is thereafter marked with an explicit rate of transmission determined as a function of the explicit rate stored in the first memory pertaining to another feedback message of the feedback messages received different from the feedback message retrieved and a rate determined from a state of congestion associated with a contention point of the network element, the feedback message retrieved being transmitted from the output once the feedback message for transmission has been so marked.
According to a third broad aspect of the present invention, a method of feedback control for adjusting a rate of message transmission over a connection in a communications network is provided. The connection comprises a source and a destination of message transmission. A forward message path begins with the source and ends with the destination and a backward message path begins with the destination and ends with the source to thereby from a closed loop for the feedback control. The communications network provides network elements through which the forward and the backward messages paths each traverse. The source is provided with instructions for setting a rate at which the source will transmit messages over the connection, the instructions being transported over the connection by feedback messages received by the source, the feedback messages so received each containing an explicit rate of transmission constituting a lowest of a plurality of explicit rates of transmission which correspond to those determined respectively from states of congestion associated with each of the network elements. The method of feedback control comprises the steps of (a) receiving a new feedback message from the backward message path at a network element trasversed by the backward message path; (b) extracting an explicit rate of transmission being carried by the new feedback message; (c) providing a feedback message for transmission from the network element at a time after steps (a) and (b) and prior to providing the new feedback message for transmission from the network element and marking the feedback message for transmission with an explicit rate of transmission determined as a function of the explicit rate extracted from the net feedback message and a rate determined from a state of congestion associated with a contention point of the network element substantially at a time when the feedback message for transmission is to be transmitted externally from the network element; and (d) immediately following the marking of the feedback message for transmission as aforesaid, transmitting the feedback message for transmission externally from the network element over the backward message path.